package day01;

public class MyTreeMap<K,V> {
    private Entry<K, V> root;
    private int size = 0;

    private class Entry<K, V>{
        K key; //按照key比较大小
        V value;
        Entry<K, V> left;
        Entry<K, V> right;
        public Entry(K key, V value){
            this.key = key;
            this.value = value;
        }
        public V addChild(K key, V value){
            //将key和当前节点的key比较大小
            //如果相等 就进行value的替换
            //如果大就添加到左侧
            //如果小就添加到右侧
            if (! (key instanceof Comparable)){
                throw new IllegalArgumentException("不可比较大小!");
            }
            Comparable c = (Comparable) key; //类型转换,才能调用compareTo方法
            //将参数 key 和 当前的节点的key比大小, result: 结果
            int result = c.compareTo(this.key);
            if (result == 0){ //相等 c 和 当前的key相等, 则替换value
                V old = this.value;
                this.value = value; //替换当前的value
                return old;
            }else if(result>0){//c 大于当前的key, 添加到右侧
                if (right == null){
                    //右侧是没有节点,就创建新节点
                    right = new Entry<>(key, value);
                    size++;
                    return null;
                }else{
                    //如果右侧已经有节点, 就象根节点一样, 为右侧添加子节点
                    return right.addChild(key, value);
                }
            }else{//c 小于当前的key, 添加到左侧
                if (left == null){
                    left = new Entry<>(key, value);
                    size++;
                    return null;
                }else{
                    return left.addChild(key, value);
                }
            }
        }

        public V get(K key) {
            if (!(key instanceof Comparable)){
                throw new IllegalArgumentException("不能比较大小");
            }
            Comparable c = (Comparable) key;
            int result = c.compareTo(this.key);
            if (result == 0){
                return value;
            } else if (result >0){
                //在右侧查找
                if (right == null){
                    return null;
                } else {
                    return right.get(key);
                }
            } else {
                //在左侧查找
                if (left == null){
                    return null;
                }else {
                    return left.get(key);
                }
            }
        }

        public void appendTo(StringBuilder builder){
            //中序遍历: 左 中 右 顺序
            // - 如果有左侧则添加左侧
            // - 添加当前节点, 中心数据
            // - 如果有右侧则添加右侧
            if(left != null){
                left.appendTo(builder);
            }
            // key:value,
            builder.append(key).append("=").append(value).append(", ");
            if (right != null){
                right.appendTo(builder);
            }
        }
    }

    /**
     * 将数据添加到集合, 如果key相同, 就进行替换
     * @param key
     * @param value
     * @return 返回被替换的value 如果没有替换就返回null
     */
    public V put(K key, V value){
        if (size == 0){
            root = new Entry<>(key, value);
            size++;
            return null;
        }
        return root.addChild(key, value);
    }

    /**
     * 根据key找到对应的value, 如果没有找到就返回null
     * @param key 被查找的key
     * @return 找到的value
     */
    public V get(K key){
        if (size == 0){
            return null;
        }
        return root.get(key);
    }

    @Override
    public String toString() {
        if(size == 0){
            return "{}";
        }
        StringBuilder builder = new StringBuilder("{");
        root.appendTo(builder);
        return builder.delete(builder.length()-2,builder.length())
                .append("}").toString();
    }
}
